package com.example.algorithm.dp;

/**
 * @author : zhy
 * @since : 2022/8/31
 * 斐波那契数
 */
public class Rabbit {
    /**
     * 方法一
     * @param n
     * @return
     */
    public int fib(int n) {
        if(n<2){
            return 1;
        }
        int a=0,b=1,c=0;
        for(int i=2;i<=n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return b;
    }


    /**
     * 方法二
     * @param n
     * @return
     */
    public int fib1(int n){
        int []dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Rabbit rabbit = new Rabbit();
        System.out.println(rabbit.fib(3));

        System.out.println("------------------------");

        System.out.println(rabbit.fib1(3));
    }
}
